package sort;

public class ShellSort {
    public static void sort(int[] nums){
        //严格按照定义来写
        //经检验，无论数组长度为奇数还是偶数，都是一共有gap组
        //希尔排序无论如何都会经过gap=1这一组,如果数组只有一个数，就不会进入循环体
        for (int gap = nums.length/2; gap>0 ; gap/=2) {
            //按组书写
            for(int i=0;i<gap;i++){
                for (int j = i; j < nums.length; j+=gap) {
                    int temp = nums[j];
                    int index = j-gap;
                    while(index>-1 && nums[index]>temp){
                        nums[index+gap] = nums[index];
                        index -= gap;
                    }
                    nums[index+gap] = temp;
                }
            }
        }
    }




    public static void shellSort(int[] nums) {
        for (int gap = nums.length / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < nums.length; i++) {
                int j = i;
                int temp = nums[j];
                if (nums[j - gap] > nums[j]) {
                    while (j - gap >= 0 && temp < nums[j - gap]) {
                        // 移动法
                        nums[j] = nums[j - gap];
                        j -= gap;
                    }
                    nums[j] = temp;
                }
            }
        }
    }
}
